package com.example.demo.study;

import cn.hutool.core.bean.BeanUtil;
import cn.hutool.core.date.DateField;
import cn.hutool.core.date.DateTime;
import cn.hutool.core.date.DateUnit;
import cn.hutool.core.date.DateUtil;
import cn.hutool.core.util.StrUtil;
import cn.hutool.crypto.digest.MD5;
import com.alibaba.fastjson.JSONObject;
import lombok.Data;
import org.springframework.security.crypto.bcrypt.BCryptPasswordEncoder;

import javax.imageio.ImageIO;
import javax.swing.filechooser.FileSystemView;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.net.URL;
import java.net.URLEncoder;
import java.nio.charset.StandardCharsets;
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.stream.Collectors;

public class Test {

    @org.junit.Test
    public void test() {
        long currentTimeMillis = System.currentTimeMillis();
        System.out.println(currentTimeMillis);
        System.out.println(1669859155L * 1000L);


        Date date = new Date(currentTimeMillis);
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        System.out.println(sdf.format(date));


        Date date1 = new Date(1669859155L * 1000);
        System.out.println(sdf.format(date1));


        DateTime dateTime = DateUtil.offsetDay(new Date(), -1);
        System.out.println(dateTime);

    }

    @org.junit.Test
    public void test1() {
        long currentTimeMillis = System.currentTimeMillis();
        System.out.println(currentTimeMillis);

        /**
         * 开始时间截 (2015-01-01)
         */
        long twepoch = 1420041600000L;
        System.out.println((currentTimeMillis - twepoch) << 22);
    }


    @org.junit.Test
    public void test3() {
//        String str = "\uD83D\uDE11";
        String str = "你好";
        System.out.println(str);
        System.out.println(str.getBytes().length);
    }


    @org.junit.Test
    public void test4() {
        boolean numeric = isNumeric("3eee");
        System.out.println(numeric);
    }

    /**
     * 判断是否是数字 是数字true  不是数字false
     *
     * @param str
     * @return
     */
    public boolean isNumeric(String str) {
        for (int i = str.length(); --i >= 0; ) {
            if (!Character.isDigit(str.charAt(i))) {
                return false;
            }
        }
        return true;
    }

    /**
     * urlEncode
     */
    @org.junit.Test
    public void urlEncode() {
        String encode = URLEncoder.encode("http://community.linkwechat.net/api/bbs/oauth/callback/weixin");
        System.out.println(encode);
    }

    @org.junit.Test
    public void test6() {
        String str = "<p><br></p><p> <img src=\\\"https://link-wechat-1251309172.cos.ap-nanjing.myqcloud.com/2023-02-28/t1677554643845-LiaTQbNwjd3ZRC9x.png\\\"></p>";
        converProductDescription(str);
    }


    @org.junit.Test
    public void test8() {
        Long str = 1677757680000L;
        Date date = new Date(str);
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        System.out.println(sdf.format(date));
    }

    @org.junit.Test
    public void test9() {
        Long str = 1677757L;
        Integer str1 = 1677757;
        System.out.println(str1.equals(str.intValue()));


        String url = "https://link-wechat-1251309172.cos.ap-nanjing.myqcloud.com/2023-03-06/t1678090960029-xSZ9ZubbXocwHUcv.png";
        String substring = url.substring(url.lastIndexOf(".") + 1);
        System.out.println(substring);

    }

    @org.junit.Test
    public void test10() {
        //写出图片
        File file = new File("C:\\Users\\Administrator\\Desktop\\测试素材\\234.jpg");
        try {
            URL url = new URL("https://link-wechat-1251309172.cos.ap-nanjing.myqcloud.com/2023-03-06/t1678090960029-xSZ9ZubbXocwHUcv.png");
            BufferedImage read = ImageIO.read(url);
            ImageIO.write(read, "jpg", file);
        } catch (IOException e) {
            e.printStackTrace();
        }

    }


    /**
     * 转换产品描述
     *
     * @param str str
     * @return {@link String}
     */
    public String converProductDescription(String str) {
        StringBuilder sb = new StringBuilder();
        List<String> imgArr = Arrays.asList(str.split("<img"));
        for (int i = 0; i < imgArr.size(); i++) {
            String img = imgArr.get(i);
            if (i != imgArr.size() - 1) {
                img = img + "<img";
            }
            if (img.indexOf("src") > 0) {
                if (img.indexOf("style=") > 0) {
                    String rgex = "style=\"(.*?)\"";
                    String rgexStr = getSubUtilSimple(img, rgex);
                    if (rgexStr.indexOf("max-width: 100%;") < 0) {
                        img = img.replace(rgexStr, rgexStr + "max-width: 100%");
                    }
                } else {
                    img = " style=\"max-width: 100%;\"" + img;
                }
            }
            sb.append(img);
        }

        System.out.println(sb.toString());
        return sb.toString();
    }


    /**
     * 返回单个字符串，若匹配到多个的话就返回第一个，方法与getSubUtil一样
     *
     * @param soap
     * @param rgex
     * @return
     */
    public String getSubUtilSimple(String soap, String rgex) {
        // 匹配的模式
        Pattern pattern = Pattern.compile(rgex);
        Matcher m = pattern.matcher(soap);
        while (m.find()) {
            return m.group(1);
        }
        return "";
    }


    @org.junit.Test
    public void test7() {
        List<Map<String, Object>> list = new ArrayList<>();
        Map<String, Object> map1 = new HashMap<>();
        map1.put("排序", "11-2");
        list.add(map1);

        Map<String, Object> map2 = new HashMap<>();
        map2.put("排序", "11-2");
        list.add(map2);

        Map<String, Object> map3 = new HashMap<>();
        map3.put("排序", "11-3");
        list.add(map3);

        Map<String, Object> map4 = new HashMap<>();
        map4.put("排序", "11-4");
        list.add(map4);

        Map<String, Object> map5 = new HashMap<>();
        map5.put("排序", "11");
        list.add(map5);

        Map<String, Object> map6 = new HashMap<>();
        map6.put("排序", "11-1");
        list.add(map6);

        Map<String, Object> map7 = new HashMap<>();
        map7.put("排序", "11-5");
        list.add(map7);

        list.sort((o1, o2) -> String.valueOf(o1.get("排序")).compareTo(String.valueOf(o2.get("排序"))));
        System.out.println(list);
    }


    @org.junit.Test
    public void test11() {
        Object[] objects = new Object[]{1, 2, 3};
        String s = JSONObject.toJSONString(objects);
        System.out.println(s);
    }

    @org.junit.Test
    public void test12() {
        List<String> list = new ArrayList();
        list.add("123");
        list.add("12322");
        String s = list.stream().findFirst().orElse(null);
        System.out.println(s);
    }


    @org.junit.Test
    public void test13() {
        Student student = new Student();
        student.setName("1");
        student.setAge("2");


        Map map = BeanUtil.copyProperties(student, Map.class);
        System.out.println(map);
    }

    @Data
    public static class Student {
        private String name;
        private String age;
    }


    @org.junit.Test
    public void test14() {
        List<Long> list = new ArrayList<>();
        list.add(0L);
        list.add(1L);
        list.add(2L);
        list.add(3L);
        list.add(4L);
        list.add(5L);

        List<Long> longs = list.subList(0, 2);
        List<Long> longs1 = list.subList(2, 6);
        System.out.println(longs);
        System.out.println(longs1);
        System.out.println(list);


    }

    @org.junit.Test
    public void test15() {
        double v = 4 * 0.5;
        System.out.println(v);

        int i = new BigDecimal(0.5).intValue();
        System.out.println(i);

        BigDecimal bigDecimal = new BigDecimal(4);
        BigDecimal divide = (new BigDecimal(30)).divide(BigDecimal.valueOf(100), 2, BigDecimal.ROUND_HALF_UP);
        int i1 = bigDecimal.multiply(divide).intValue();
        System.out.println(i1);
    }

    @org.junit.Test
    public void test16() {
        DateTime date = DateUtil.date(new Date());
        System.out.println(date);
        DateTime dateTime = DateUtil.offsetDay(new Date(), 3);
        System.out.println(dateTime);

        DateTime dateTime1 = DateUtil.beginOfDay(dateTime);
        System.out.println(dateTime1);

        DateTime dateTime2 = DateUtil.endOfDay(dateTime);
        System.out.println(dateTime2);

        DateTime dateTime3 = DateUtil.beginOfDay(date);
        System.out.println(dateTime3);

        DateTime dateTime4 = new DateTime(dateTime3);

        System.out.println(dateTime3 == dateTime4);
        DateTime offset = dateTime4.offset(DateField.HOUR_OF_DAY, 8);
        System.out.println(offset);

        System.out.println(dateTime3);

    }


    @org.junit.Test
    public void test17() {
        Student student = null;
        String age = Optional.ofNullable(student).orElse(null).getAge();
        System.out.println(age);

    }


    @org.junit.Test
    public void test18() {
        ArrayList<Long> list = new ArrayList<>();
        List<Long> collect = list.stream().filter(i -> i.equals(1)).collect(Collectors.toList());

        System.out.println(collect);

    }

    @org.junit.Test
    public void test19() {
        int i = 0 % 3;

        System.out.println(i);

    }

    @org.junit.Test
    public void test20() throws InterruptedException {
        Date date = new Date();
        Thread.sleep(1000);
        Date date2 = new Date();
        DateTime date1 = DateUtil.date(date);
        DateTime date3 = DateUtil.date(date2);
        long l = DateUtil.betweenMs(date1, date3);
        System.out.println(l);

        long l1 = date2.getTime() - date.getTime();
        System.out.println(l1);

        long l2 = date.getTime() + 229535362;
        DateTime date4 = DateUtil.date(l2);
        System.out.println(date4.toDateStr());
        System.out.println(date4.toTimeStr());


    }

    @org.junit.Test
    public void test21() {
        //当前时间
        DateTime date = DateUtil.date();
        System.out.println(date.toDateStr() + " " + date.toTimeStr());

        //第二天凌晨
        DateTime dateTime = DateUtil.offsetDay(date, 1);
        DateTime dateTime2 = DateUtil.beginOfDay(dateTime);
        System.out.println(dateTime2.toDateStr() + " " + dateTime2.toTimeStr());

        //A框的截止日期
        DateTime dateTime1 = DateUtil.offsetDay(dateTime2, 0);
        DateTime dateTime3 = DateUtil.endOfDay(dateTime1);
        System.out.println(dateTime3.toDateStr() + " " + dateTime3.toTimeStr());

        //A框的提醒时间
        DateTime offset = dateTime1.offset(DateField.HOUR, 8);
        System.out.println(dateTime1.toDateStr() + " " + offset.toTimeStr());

    }

    @org.junit.Test
    public void test22() {
        String str = "{\"endTime\":1685059200000,\"isProtect\":false,\"leadsId\":165,\"seaId\":34,\"type\":1,\"userId\":1650340569282646016,\"version\":0}";

        WeLeadsCenterGtasksSaveAndSendParam param = new WeLeadsCenterGtasksSaveAndSendParam();
        param.setEndTime(DateTime.now());
        param.setIsProtect(false);
        param.setLeadsId(1L);
        param.setSeaId(8L);
        param.setType(1);
        param.setUserId(111111111111L);
        param.setVersion(0);

        String jsonString = JSONObject.toJSONString(param);
        WeLeadsCenterGtasksSaveAndSendParam weLeadsCenterGtasksSaveAndSendParam = JSONObject.parseObject(jsonString, WeLeadsCenterGtasksSaveAndSendParam.class);
        System.out.println(weLeadsCenterGtasksSaveAndSendParam);
    }

    @org.junit.Test
    public void test23() {
        String str1 = ".";
        String str = "你";
        int length = str1.getBytes(StandardCharsets.UTF_8).length;
        System.out.println(length);
    }

    @org.junit.Test
    public void test24() {
        final String url = "你好：{},{}";
        String format = StrUtil.format(url, 111, 2222, 3333);
        System.out.println(format);
    }

    @org.junit.Test
    public void test25() {
        String str = "你好";
        String jsonString = JSONObject.toJSONString(str);
        System.out.println(jsonString);
        String s = JSONObject.parseObject(jsonString, String.class);
        System.out.println(s);
    }

    @org.junit.Test
    public void test26() {
        File desktopDir = FileSystemView.getFileSystemView().getHomeDirectory();

        String desktopPath = desktopDir.getAbsolutePath();
        System.out.println(desktopPath);

        MD5 md5 = MD5.create();
        String password = md5.digestHex(123456 + "-" + "Ai18");
        System.out.println(password);
    }

    @org.junit.Test
    public void test27() throws ParseException {
//        String date = "2026-05-06";
//        String format = "yyyy-MM-dd HH:00:00";
//        Date parse = new SimpleDateFormat(format).parse(date);

        DateTime now = DateTime.now();
        DateTime dateTime = new DateTime("2023-08-21 10:10:10", "yyyy-MM-dd HH:mm:ss");
        long between = DateUtil.between(now, dateTime, DateUnit.MS, false);
        System.out.println(between);


    }

    @org.junit.Test
    public void test28() {
        char c = 'a';
        String s = Integer.toBinaryString(c);
        System.out.println(s);
    }

    @org.junit.Test
    public void test29() {
        String str = "王";
        byte[] bytes = str.getBytes();
        for (int i = 0; i < bytes.length; i++) {
            System.out.println(bytes[i]);

            String s = Integer.toBinaryString((byte) bytes[i]);
            System.out.println(s);
            System.out.println(s.length());
        }
    }


    @org.junit.Test
    public void test30() {
        System.out.println(new BCryptPasswordEncoder().encode("qy@2023#203"));

    }

    @org.junit.Test
    public void test31() {
        byte b = -128;
        int i = Byte.toUnsignedInt(b);
        System.out.println(i);

        char c = '\u03c0';
        System.out.println(c);

        char minValue = Character.MIN_VALUE;
        char maxValue = Character.MAX_VALUE;
        System.out.println(Integer.valueOf(minValue));
        System.out.println(Integer.valueOf(maxValue));

        boolean $ = Character.isJavaIdentifierStart('$');
        System.out.println($);

//        int i1 = 1/0;

        double v = 0.1 / 0;
        System.out.println(v);
    }

    @org.junit.Test
    public void test32() {
        int i = (0 + -16) % 12;
        System.out.println(i);

        int i1 = Math.floorMod((0 + -16), 12);
        System.out.println(i1);

        String str = "green";
        String s = new String("green");
        System.out.println(str.equals(s));


        String str1 = "green";
        String s1 = str1.substring(0, 3) + "en";
        System.out.println(str1 == s1);

        str1 = "你好";
        int length = str1.length();
        System.out.println(length);
        int count = str1.codePointCount(0, str1.length());
        System.out.println(count);

        char c = str1.charAt(1);
        System.out.println(c);
        int i2 = str1.codePointAt(1);
        System.out.println(i2);

        System.out.printf("%,.2f", 123111.111);
        System.out.println();

        System.out.printf("%tF", new Date());

    }

    @org.junit.Test
    public void test33() throws FileNotFoundException {
        File file = new File("C:\\Users\\Administrator\\Desktop\\lw组件新环境.txt");
        Scanner scanner = new Scanner(file, StandardCharsets.UTF_8.toString());
        while (scanner.hasNext()) {
            String s = scanner.nextLine();
            System.out.println(s);
        }
    }


    @org.junit.Test
    public void test34() {

        BigInteger bigInteger = new BigInteger("11111111111111111111111111111111111111111111111111111111111111");
        BigInteger add = bigInteger.add(new BigInteger("11111111111111111111111111111111111111111111111111111111111111"));
        System.out.println(add);
    }

    @org.junit.Test
    public void test35() {
        problem1(new int[]{1, 1, 2, 2, 4});
    }

    @org.junit.Test
    public void test37() {
        int i = strStr("abc", "c");
        System.out.println(i);
    }

    public int strStr(String haystack, String needle) {
        if (haystack.length() == needle.length()) {
            return haystack.equals(needle) ? 0 : -1;
        }

        int i1 = haystack.length() - needle.length();
        for (int i = 0; i <= i1; i++) {
            String substring = haystack.substring(i, i + needle.length());
            if (substring.equals(needle)) {
                return i;
            }
        }
        return -1;
    }


    @org.junit.Test
    public void test36() {
        char theDifference = findTheDifference("abcd", "abcde");
        System.out.println(theDifference);
    }

    @org.junit.Test
    public void test38() {
        boolean anagram = isAnagram("rat", "car");
        System.out.println(anagram);
    }

    @org.junit.Test
    public void test39() {
        int i = romanToInt("MCMXCIV");
        System.out.println(i);

    }

    public int romanToInt(String s) {
        int result = 0;
        int i = 0;
        while (i < s.length()) {
            char c = s.charAt(i);
            if (c == 'I') {
                if (i + 1 < s.length() && s.charAt(i + 1) == 'V') {
                    result += 4;
                    i++;
                } else if (i + 1 < s.length() && s.charAt(i + 1) == 'X') {
                    result += 9;
                    i++;
                } else {
                    result += 1;
                }
            } else if (c == 'V') {
                result += 5;
            } else if (c == 'X') {
                if (i + 1 < s.length() && s.charAt(i + 1) == 'L') {
                    result += 40;
                    i++;
                } else if (i + 1 < s.length() && s.charAt(i + 1) == 'C') {
                    result += 90;
                    i++;
                } else {
                    result += 10;
                }
            } else if (c == 'L') {
                result += 50;
            } else if (c == 'C') {
                if (i + 1 < s.length() && s.charAt(i + 1) == 'D') {
                    result += 400;
                    i++;
                } else if (i + 1 < s.length() && s.charAt(i + 1) == 'M') {
                    result += 900;
                    i++;
                } else {
                    result += 100;
                }
            } else if (c == 'D') {
                result += 500;
            } else if (c == 'M') {
                result += 1000;
            }
            i++;
        }
        return result;
    }


    @org.junit.Test
    public void test40() {
        String s = intToRoman(1784);
        System.out.println(s);
    }

    public String intToRoman(int num) {
        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        StringBuffer roman = new StringBuffer();
        for (int i = 0; i < values.length; ++i) {
            int value = values[i];
            String symbol = symbols[i];
            while (num >= value) {
                num -= value;
                roman.append(symbol);
            }
            if (num == 0) {
                break;
            }
        }
        return roman.toString();
    }

    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        int[] ints = new int[26];
        for (int i = 0; i < s.length(); i++) {
            ints[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < t.length(); i++) {
            ints[t.charAt(i) - 'a']--;
        }

        for (int i = 0; i < ints.length; i++) {
            if (ints[i] != 0) {
                return false;
            }
        }
        return true;

    }

    /**
     * 一个数组中有一个数出现了奇数次，其他数都出现了偶数次，寻找该奇数
     *
     * @param arr 数组
     */

    public static void problem1(int[] arr) {
        int res = 0;
        for (int value : arr) {
            res ^= value;
        }


        System.out.println(res);
    }


    public char findTheDifference(String s, String t) {
        int i = 0;
        while (i < s.length()) {
            char c = s.charAt(i);
            t = t.replaceFirst(String.valueOf(c), "");
            i++;
        }
        return t.charAt(0);
    }


    private String mergeAlternately(String word1, String word2) {
        Objects.requireNonNull(word1);
        Objects.requireNonNull(word2);
        int length = word1.length();
        int length1 = word2.length();

        StringBuilder sb = new StringBuilder();

        int i = 0, j = 0;

        while (i < length && i < length1) {
            sb.append(word1.charAt(i)).append(word2.charAt(i));
            i++;
            j++;
        }

        while (i < length) {
            sb.append(word1.charAt(i++));
        }

        while (j < length) {
            sb.append(word2.charAt(i++));
        }

        return sb.toString();
    }


    @org.junit.Test
    public void test41() {
        int[] nums = {0, 1, 0, 3, 12};
        long l = System.currentTimeMillis();
        moveZeroes1(nums);
        System.out.println(System.currentTimeMillis() - l);
        System.out.println(Arrays.toString(nums));
    }

    public void moveZeroes(int[] nums) {
        int j = nums.length;
        int i = 0;
        while (i < j) {
            if (nums[i] == 0) {
                int l = i;
                for (int k = i; k < j - 1; k++) {
                    nums[k] = nums[k + 1];
                }
                nums[j - 1] = 0;
                j--;
                i = l;
            } else {
                i++;
            }
        }
    }

    public void moveZeroes1(int[] nums) {
        int i = 0, j = 0;
        while (i < nums.length) {
            if (nums[i] != 0) {
                int t = nums[i];
                nums[j] = nums[i];
                nums[i] = t;
                j++;
            }
            i++;
        }
    }

    public void moveZeroes2(int[] nums) {
        int i = 0, j = 0;
        while (i < nums.length) {
            if (nums[i] != 0) {
                nums[j] = nums[i];
                j++;
            }
            i++;
        }

        while (j < nums.length) {
            nums[j] = 0;
            j++;
        }

    }

    @org.junit.Test
    public void test42() {
        int[] nums = {3, 2, 2, 3};
        System.out.println(removeElement(nums, 3));
    }

    public int removeElement(int[] nums, int val) {
        int i = 0, j = 0;
        for (int n = 0; n < nums.length; n++) {
            if (nums[n] != val) {
                nums[j] = nums[n];
                j++;
            }
        }

        return j;

    }


    @org.junit.Test
    public void test43() {
        //int[] nums = {1, 2, 6, 3, 4, 5, 6};

        ListNode listNode5 = new ListNode();
        listNode5.val = 6;

        ListNode listNode4 = new ListNode();
        listNode4.val = 5;
        listNode4.next = listNode5;

        ListNode listNode3 = new ListNode();
        listNode3.val = 4;
        listNode3.next = listNode4;

        ListNode listNode2 = new ListNode();
        listNode2.val = 3;
        listNode2.next = listNode3;

        ListNode listNode1 = new ListNode();
        listNode1.val = 6;
        listNode1.next = listNode2;

        ListNode listNode = new ListNode();
        listNode.val = 2;
        listNode.next = listNode1;

        ListNode head = new ListNode();
        head.val = 1;
        head.next = listNode;

        removeElements(head, 6);
    }

    @org.junit.Test
    public void test44() {

        ListNode listNode3 = new ListNode();
        listNode3.val = 7;

        ListNode listNode2 = new ListNode();
        listNode2.val = 7;
        listNode2.next = listNode3;

        ListNode listNode1 = new ListNode();
        listNode1.val = 7;
        listNode1.next = listNode2;

        ListNode listNode = new ListNode();
        listNode.val = 7;
        listNode.next = listNode1;

        ListNode head = new ListNode();
        head.val = 7;
        head.next = listNode;
//        bianli(head);
        removeElements(head, 7);
    }

    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return head;
        }
        ListNode node = new ListNode();
        if (head.val == val) {
            node = head.next;
        } else {
            node = head;
        }
        do {
            head = head.next;
            if (head.val == val) {
                head = head.next;
            }
        } while (head.next != null);

        return node;
    }

    public void bianli(ListNode head) {
        System.out.println(head.val);
        do {
            head = head.next;
            System.out.println(head.val);
        } while (head.next != null);
    }


    @org.junit.Test
    public void test45() {
        int[] num = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
        int[] ints = plusOne1(num);
        System.out.println(Arrays.toString(ints));
    }

    public int[] plusOne(int[] digits) {
        StringBuilder sb = new StringBuilder();
        for (int digit : digits) {
            sb.append(digit);
        }
        String s1 = sb.toString();
        BigDecimal integer = new BigDecimal(s1);
        BigDecimal add = integer.add(BigDecimal.ONE);
        String s = add.toString();

        String[] split = s.split("");
        int[] result = new int[s.length()];
        for (int i1 = 0; i1 < split.length; i1++) {
            result[i1] = Integer.parseInt(split[i1]);
        }
        return result;
    }

    public int[] plusOne1(int[] digits) {
        for (int i = digits.length - 1; i >= 0; i--) {
            if (digits[i] != 9) {
                digits[i]++;
                for (int j = i + 1; j < digits.length; j++) {
                    digits[j] = 0;
                }
                return digits;
            }
        }
        int[] temp = new int[digits.length + 1];
        temp[0] = 1;
        return temp;
    }


    @org.junit.Test
    public void test46() {
        int[] num = {0};
        List<Integer> integers = addToArrayForm(num, 1000);
        System.out.println(integers.toString());
    }

    public List<Integer> addToArrayForm(int[] num, int k) {
        List<Integer> result = new ArrayList<>();
        int carry = 0;
        for (int i = num.length - 1; i >= 0; i--) {
            int i1 = k % 10;
            k = k / 10;
            int i2 = num[i] + i1 + carry;
            if (i2 >= 10) {
                num[i] = i2 - 10;
                carry = 1;
            } else {
                num[i] = i2;
                carry = 0;
            }
            result.add(num[i]);
            if (carry == 0 && k == 0) {
                break;
            }
        }
        if (carry == 1 || k != 0) {
            k = k + carry;
            while (k / 10 > 0) {
                result.add(k % 10);
                k = k / 10;
            }
            if (k != 0) {
                result.add(k);
            }
        }
        Collections.reverse(result);
        return result;
    }


    public List<Integer> addToArrayForm1(int[] num, int k) {
        int carry = 0;
        for (int i = num.length - 1; i >= 0; i--) {
            int i1 = k % 10;
            k = k / 10;
            int i2 = num[i] + i1 + carry;
            if (i2 >= 10) {
                num[i] = i2 - 10;
                carry = 1;
            } else {
                num[i] = i2;
                carry = 0;
            }
            if (carry == 0 && k == 0) {
                break;
            }
        }
        List<Integer> result = new ArrayList<>();
        if (carry == 1 || k != 0) {
            int i = k + carry;
            if (i >= 10) {
                String[] split = String.valueOf(i).split("");
                for (String s : split) {
                    result.add(Integer.parseInt(s));
                }
            } else {
                result.add(i);
            }

        }
        for (int i = 0; i < num.length; i++) {
            result.add(num[i]);
        }
        return result;
    }


    public List<Integer> addToArrayForm2(int[] num, int k) {
        List<Integer> result = new ArrayList<>();
        for (int i = num.length - 1; i >= 0; i--) {
            int i2 = num[i] + k % 10;
            k /= 10;
            if (i2 >= 10) {
                i2 = i2 - 10;
                k++;
            }
            result.add(i2);
        }
        while (k > 0) {
            result.add(k % 10);
            k = k / 10;
        }
        Collections.reverse(result);
        return result;
    }

    public List<Integer> addToArrayForm3(int[] num, int k) {
        List<Integer> result = new ArrayList<>();
        for (int i = num.length - 1; i >= 0 || k > 0; i--, k /= 10) {
            if (i > 0) {
                k += num[i];
            }
            result.add(k % 10);
        }
        Collections.reverse(result);
        return result;
    }


    public boolean canMakeArithmeticProgression(int[] arr) {

        Arrays.sort(arr);
        int i2 = arr[0] - arr[1];
        for (int i = 0; i < arr.length - 1; i++) {
            int i1 = arr[i] - arr[i + 1];
            if (i1 != i2) {
                return false;
            }
        }
        return true;

    }


    public int arraySign(int[] nums) {
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                return 0;
            }
            if (nums[i] < 0) {
                result++;
            }
        }
        return result % 2 == 0 ? 1 : -1;
    }

    public int arraySign1(int[] nums) {
        int result = 1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                return 0;
            }
            if (nums[i] < 0) {
                result = -result;
            }
        }
        return result;
    }


    @org.junit.Test
    public void test47() {
        String s = addBinary("100", "110010");
        System.out.println(s);
    }

    public String addBinary(String a, String b) {
        int carry = 0;
        StringBuilder sb = new StringBuilder();
        for (int i = a.length() - 1, j = b.length() - 1; i >= 0 || j >= 0; i--, j--) {
            int i1 = 0;
            if (i >= 0 && j >= 0) {
                i1 = a.charAt(i) - '0' + b.charAt(j) - '0' + carry;
            } else if (i >= 0) {
                if (carry == 1) {
                    i1 = a.charAt(i) - '0' + carry;
                } else {
                    sb.append(new StringBuffer().append(a, 0, i + 1).reverse());
                    return sb.reverse().toString();
                }
            } else if (j >= 0) {
                if (carry == 1) {
                    i1 = b.charAt(j) - '0' + carry;
                } else {
                    sb.append(new StringBuffer().append(b, 0, j + 1).reverse());
                    return sb.reverse().toString();
                }
            }
            sb.append(i1 % 2);
            carry = i1 / 2;
        }
        if (carry == 1) {
            sb.append(carry);
        }
        return sb.reverse().toString();
    }

    public String addBinary1(String a, String b) {
        int carry = 0;
        StringBuilder sb = new StringBuilder();
        for (int i = a.length() - 1, j = b.length() - 1; i >= 0 || j >= 0; i--, j--) {
            int i1 = 0;
            if (i >= 0 && j >= 0) {
                i1 = a.charAt(i) - '0' + b.charAt(j) - '0' + carry;
            } else if (i >= 0) {

                i1 = a.charAt(i) - '0' + carry;

            } else if (j >= 0) {
                i1 = b.charAt(j) - '0' + carry;
            }
            sb.append(i1 % 2);
            carry = i1 / 2;
        }
        if (carry == 1) {
            sb.append(carry);
        }
        return sb.reverse().toString();
    }


    public boolean checkStraightLine(int[][] coordinates) {
        int deltaX = coordinates[0][0];
        int deltaY = coordinates[0][1];
        int n = coordinates.length;

        for (int i = 0; i < n; i++) {
            coordinates[i][0] -= deltaX;
            coordinates[i][1] -= deltaY;
        }

        int A = coordinates[1][0];
        int B = coordinates[1][1];

        for (int i = 2; i < n; i++) {
            int x = coordinates[i][0];
            int y = coordinates[i][1];
            if (B * x - A * y != 0) {
                return false;
            }

        }
        return true;
    }


    @org.junit.Test
    public void test48() {
        int[] nums = {757, 341, 254, 499, 96, 622, 685, 514, 482, 655, 680, 593, 407, 660, 330, 469, 841, 335, 53, 764, 341, 918, 290, 667, 47, 725, 319, 135, 118, 636, 145, 540, 363, 708, 658, 735, 999, 306, 531, 427, 393, 872, 30, 838, 873, 710, 438, 364, 95, 567, 737, 510, 961, 881, 37, 567, 464, 991, 587, 363, 25, 532, 565, 116, 876, 479, 805, 908, 71, 581, 262, 881, 657, 734, 60, 111, 718, 739, 950, 349, 588, 963, 947, 213, 356, 429, 446, 420, 706, 221, 709, 948, 855, 811, 763, 978, 704, 384, 601, 920, 170, 864, 785, 308, 983, 524, 711, 233, 537, 657, 682, 728, 37, 131, 521, 783, 130, 669, 574, 503, 453, 712, 216, 976, 764, 803, 921, 747, 261, 329, 500, 361, 485, 757, 173, 47, 211, 730, 171, 254, 115, 936, 111, 837, 35, 64, 244, 481, 385, 300, 450, 682, 339, 423, 927, 835, 332, 827, 624, 212, 180, 802, 873, 535, 528, 947, 882, 549, 574, 81, 415, 645, 307, 826, 924, 405, 800, 791, 620, 337, 517, 488, 981, 920, 131, 367, 39, 45, 686, 256, 781, 298, 303, 146, 478, 297, 33, 767, 247, 195, 664, 763, 65, 127, 790, 424, 678, 238, 810, 944, 285, 700, 595, 432, 968, 497, 288, 15, 995, 855, 541, 712, 635, 938, 855, 784, 638, 50, 584, 857, 620, 495, 337, 903, 1000, 407, 687, 520, 406, 447, 586, 209, 53, 869, 383, 80, 311, 928, 545, 916, 16, 219, 517, 226, 31, 201, 830, 753, 324, 989, 701, 976, 713, 228, 227, 391, 268, 301, 674, 690, 994, 224, 851, 638, 117, 341, 146, 235, 676, 172, 429, 744, 806, 899, 549, 633, 148, 181, 948, 381, 861, 93, 143, 974, 366, 901, 517, 161, 166, 492, 355, 441, 388, 407, 17, 34, 472, 592, 32, 184, 388, 156, 400, 764, 435, 968, 798, 130, 277, 687, 955, 476, 135, 644, 313, 303, 28, 635, 667, 817, 651, 341, 98, 637, 870, 141, 695, 425, 997, 467, 961, 622, 624, 987, 913, 256, 781, 338, 304, 144, 253, 137, 860, 377, 162, 476, 632, 181, 616, 671, 486, 900, 447, 697, 389, 787, 858, 495, 574, 329, 583, 423, 784, 382, 715, 939, 515, 476, 710, 558, 872, 52, 133, 524, 240, 792, 506, 958, 738, 138, 378, 836, 469, 238, 659, 54, 346, 458, 971, 536, 44, 34, 494, 224, 573, 443, 90, 804, 415, 90, 48, 690, 713, 302, 243, 276, 636, 611, 226, 933, 788, 147, 94, 691, 453, 414, 518, 322, 939, 961, 551, 338, 79, 1000, 186, 671, 404, 675, 653, 965, 218, 268, 410, 656, 793, 615, 884, 911, 55, 360, 297, 526, 913, 120, 301, 551, 604, 454, 545, 531, 3, 642, 85, 67, 394, 235, 731, 862, 599, 804, 574, 951, 981, 855, 226, 19, 336, 259, 441, 342, 305, 250, 727, 78, 985, 672, 110, 78, 719, 57, 375, 449, 750, 593, 497, 376, 930, 67, 822, 750, 10, 170, 371, 465, 5, 542, 965, 388, 508, 888, 873, 337, 590, 863, 425, 812, 347, 41, 306, 813, 413, 343, 613, 12, 978, 81, 227, 78, 560, 164, 921, 847, 279, 113, 663, 290, 474, 395, 390, 241, 206, 804, 568, 831, 391, 83, 501, 222, 823, 171, 1000, 290, 513, 343, 706, 444, 303, 606, 217, 25, 290, 619, 702, 935, 699, 27, 774, 916, 531, 682, 896, 834, 14, 729, 454, 372, 542, 189, 960, 958, 508, 710, 199, 981, 207, 158, 215, 904, 322, 302, 436, 922, 449, 627, 370, 409, 33, 138, 85, 470, 73, 177, 724, 723, 441, 278, 910, 2164, 14, 217, 310, 65, 606, 488, 477, 120, 894, 495, 149, 891, 481, 716, 297, 912, 89, 981, 414, 715, 398, 844, 890, 746, 970, 767, 821, 760, 291, 876, 423, 869, 845, 580, 959, 265, 882, 217, 966, 537, 526, 557, 911, 662, 991, 579, 358, 636, 405, 537, 913, 441, 267, 892, 376, 657, 627, 99, 664, 359, 549, 941, 520, 65, 759, 550, 198, 207, 284, 887, 853, 581, 23, 364, 394, 754, 936, 532, 480, 16203, 965, 531, 429, 72, 963, 640, 365, 797, 349, 219, 235, 571, 282, 732, 976, 625, 277, 298, 726, 619, 668, 917, 598, 895, 489, 128, 365, 701, 537, 68, 27, 32, 546, 169, 323, 548, 38, 819, 498, 276, 498, 520, 959, 95, 202, 615, 387, 451, 429, 255, 572, 19, 61, 496, 584, 142, 977, 1531, 45, 874, 442, 288, 66, 938, 929, 532, 786, 66, 734, 607, 405, 502, 597, 241, 669, 758, 445, 955, 708, 894, 875, 798, 993, 818, 336, 215, 631, 574, 661, 422, 489, 60, 23, 90, 51, 41, 526, 489, 231, 860, 635, 345, 865, 519, 350, 426, 755, 457, 999, 841, 942, 336, 943, 414, 526, 262, 393, 749, 967, 55, 115, 619, 446, 44, 184, 804, 910, 737, 599, 891, 851, 752, 327, 1000, 977, 543, 942, 985, 757, 106, 411, 343, 370, 623, 34, 625, 60, 754, 601, 434, 94, 187, 716, 451, 310, 379, 700, 362, 543, 528, 389, 454, 950, 83, 508, 729, 503, 688, 1000, 787, 3891, 903, 105, 482, 750, 843, 969, 841, 478, 136, 971, 260, 439, 753, 232, 233, 398, 134, 885, 342, 209, 253, 426, 656, 154, 299, 567, 74, 136, 630, 979, 884, 725, 472, 943, 78, 289, 962, 173, 535, 318, 157, 939, 39, 976, 443, 15, 107, 259, 269, 146, 690, 79, 506, 523, 546, 170, 776, 736, 721, 569, 962, 553, 507, 6, 311, 527, 300, 997, 553, 174, 877, 244, 540, 818, 673, 980, 518, 913, 257, 82, 962, 264, 130, 79, 425, 871, 808, 823, 627, 928, 461, 709, 218, 740, 822, 665, 729, 994, 614, 298, 36, 82, 601, 409, 488, 384, 869, 818, 74, 255, 11, 512, 75, 572, 78, 320, 868, 803, 49, 277, 439, 177, 378, 647, 290, 280, 923, 776, 622, 203, 523, 824, 179, 68, 867, 328, 646, 145, 114, 496, 234, 599, 335, 645, 221, 557, 561, 797, 188, 688, 697, 351, 91, 965, 285, 485, 207, 774, 33, 87, 167, 926, 249, 906, 989, 523, 985, 14, 188, 64, 507, 205, 450, 725, 282, 891, 677, 84, 955, 754, 810, 91, 492, 910, 383, 863, 941, 812, 859, 514, 757, 54, 126, 45, 413, 938, 647, 809, 620, 307, 225, 628, 41, 113, 757, 552, 578, 877, 607, 955, 192, 937, 901, 146, 815, 67, 144, 806, 240, 199, 705, 650, 60, 976, 917, 694, 548, 962, 985, 255, 785, 939, 530, 997, 400, 4, 832, 353, 202, 734, 605, 408, 927, 387, 947, 34, 712, 516, 896, 508, 513, 81, 862, 960, 931, 111667, 838, 569, 866, 270, 290, 396, 24, 496, 426, 826, 358, 859, 475, 88, 510, 902, 748, 648, 58, 351, 710, 885, 173, 247, 937, 874, 597, 487, 53, 365, 498, 352, 869, 659, 458, 50, 774, 251, 672, 930, 864, 367, 675, 548, 922, 860, 769, 472, 73, 933, 29, 259, 412, 161, 380, 82, 153, 832, 948, 257, 521, 671, 883, 173, 388, 639, 313, 485, 54, 951, 818, 994, 81, 51, 905, 959, 231, 543, 730, 954, 672, 73, 562, 157, 263, 10003, 596, 834, 690, 210, 231, 185, 180, 581, 883, 459, 238, 208, 98, 988, 418, 806, 321, 985, 183, 749, 427, 538, 491, 51, 74, 306, 722, 28, 399, 268, 611, 441, 10, 321, 849, 733, 228, 735, 411, 883, 345, 751, 753, 896, 91, 627, 737, 969, 529, 274, 56, 168, 716, 789, 132, 176, 616, 69, 319, 525, 284, 530, 68, 23, 214, 617, 628, 68, 718, 526, 408, 851, 636, 743, 142, 237, 930, 110, 199, 158, 598, 323, 847, 621, 392, 982, 112, 515, 309, 504, 129, 915, 328, 328, 677, 722, 427, 14, 608, 737, 865, 469, 961, 465, 413, 803, 875, 161, 561, 497, 114, 786, 293, 436, 999, 247, 410, 845, 575, 444, 454, 692, 746, 965, 423, 711, 579, 614, 405, 643, 132, 466, 347, 152, 474, 215, 645, 369, 369, 576, 603, 305, 807, 799, 720, 958, 845, 904, 292, 91, 764, 82, 99, 408, 816, 260, 982, 595, 437, 301, 261, 438, 871, 429, 864, 538, 765, 702, 380, 792, 713, 692, 103, 668, 554, 106, 448, 41, 514, 668, 847, 68, 812, 414, 666, 825, 548, 882, 531, 65, 260, 317, 85, 180772, 266, 585, 210, 13, 437, 436, 792, 653, 494, 156, 845, 29, 493, 994, 225, 184, 397, 48, 733, 851, 496, 42571, 34, 103, 686, 638, 666, 604, 99, 615, 481, 752, 508, 129, 445, 486, 528, 412, 803, 128, 63, 317, 796, 750, 394, 654, 739, 528, 869, 831, 341, 713, 638, 229, 329, 548, 641, 907, 288, 326, 202, 875, 867, 506, 494, 637, 840, 486, 150, 996, 991, 293, 170, 842, 790, 471, 707, 298, 269, 768, 961, 219, 679, 968, 955, 908, 458, 59, 640, 704, 785, 524, 427, 679, 857, 836, 917, 154, 24, 485, 565, 30, 776, 688, 54, 161, 158, 433, 211, 220, 947, 414, 819, 611, 873, 315, 334, 690, 888, 63, 487, 135, 608, 589, 121, 761, 394, 369, 177, 197, 101, 192, 363, 62, 330, 198, 485, 930, 693, 161, 214, 91, 395, 313, 1000, 949, 592, 65, 28, 886, 393, 359, 188, 698, 532, 824, 753, 506, 190, 409, 363, 13, 932, 630, 734, 84, 789, 523, 512, 593, 814, 324, 705, 814, 104, 579, 162, 648, 673, 974, 507, 882, 700, 714, 892, 41, 103, 129, 912, 491, 891, 5, 413, 233, 442, 997, 469, 141, 695, 680, 357, 449, 874, 421, 2, 351, 570, 319, 69, 814, 266, 540, 165, 443, 618, 980, 854, 18, 941, 565, 943, 110, 977, 255, 889, 810, 239, 216, 430, 566, 760, 236, 581, 808, 483, 926, 68, 368, 990, 987, 604, 926, 487, 197, 935, 502, 405, 639, 727, 385, 906, 762, 460, 148, 727, 270, 175, 546, 735, 160, 459, 828, 735, 915, 326, 102, 772, 405, 208, 35, 496, 691, 187, 851, 543, 63, 13, 393, 857, 14, 399, 668, 942, 554, 910, 411, 952, 620, 760, 103, 669, 416, 985, 408, 787, 830, 666, 570, 950, 944, 723, 791, 422, 448, 565, 549, 819, 221, 282, 872, 47, 850, 667, 159, 102, 223, 831, 330, 24, 470, 701, 312, 787, 111, 281, 432, 967, 551, 831, 604, 875, 467, 533, 773, 196, 365, 363, 688, 885, 951, 391, 370, 648, 824, 600, 177, 477, 811, 290, 882, 297, 128, 862, 714, 99, 578, 905, 214, 920, 810, 426, 915, 786, 233, 743, 115, 436, 559, 137, 651, 172, 691, 845, 257, 733, 179, 991, 730, 345, 691, 534, 220, 128, 143, 265, 156, 711, 833, 193, 301, 129, 407, 819, 480, 42, 992, 474, 746, 46, 230, 38, 208, 579, 886, 854, 62, 782, 469, 201, 709, 334, 214, 400, 294, 211, 933, 848, 503, 468, 179, 702, 452, 645, 569, 82, 965, 833, 33, 962, 941, 527, 467, 536, 243, 576, 775, 353, 954, 940, 984, 667, 104, 160, 467, 607, 703, 451, 68, 333, 780, 29, 912, 373, 993, 695, 845, 682, 176, 29, 869, 42, 846, 898, 144, 60, 327, 283, 568, 746, 498, 176, 251, 933, 37, 832, 189, 475, 983, 156, 836, 522, 579, 637, 249, 294, 609, 115, 634, 492, 764, 381, 831, 698, 682, 410, 854, 509, 754, 116, 857, 312, 774, 959, 918, 943, 8, 573, 733, 241, 831, 319, 783, 193, 510, 943, 455, 977, 899, 109, 741, 37, 90, 47, 258, 219, 150, 750, 91, 473, 440, 768, 21, 864, 125, 404, 888, 120, 552, 551, 576, 704, 357, 896, 516, 156, 952, 577, 900, 168, 931, 731, 893, 628, 524, 66, 884, 292525, 547, 735, 899, 975, 498, 406, 151, 564, 827, 363, 862, 607, 130, 573, 793, 332, 818, 762, 418, 988, 288, 480, 141, 319, 678, 278, 516, 105, 849, 319, 961, 908, 751, 118, 825, 132, 757, 631, 294, 156, 586, 704, 42, 837, 464, 807, 52, 454, 818, 58, 491, 654, 113, 218, 959, 488, 868, 799, 131, 154, 192, 390, 199, 424, 46, 782, 540, 108, 558, 403, 327, 312, 726, 184, 805, 194, 423, 383, 260, 242, 9, 723, 142, 608, 579, 879, 560, 378, 419, 452, 992, 626, 496, 739, 148, 265, 791, 966, 937, 623, 754, 166, 30, 338, 35, 48, 322, 868, 552, 820, 354, 70, 471, 350, 746, 469, 53, 705, 870, 22, 72, 227, 856, 311, 33, 282, 697, 400, 25, 472, 967, 207, 863, 753, 583, 569, 954, 608, 768, 579, 462, 473, 154, 581, 234, 83, 467, 386, 64, 731, 446, 91, 610, 856, 880, 770, 446, 3, 199, 413, 384, 476, 427, 574, 641, 455, 46, 221, 565, 985, 457, 971, 805, 248, 899, 195, 50, 885, 872, 27, 112, 545, 696, 537, 388, 698, 612, 647, 923, 399, 177, 920, 621, 627, 768, 442, 684, 288, 414, 537, 573, 231, 476, 356, 222, 923, 759, 633, 858, 247, 452, 273, 632, 133, 449, 504, 859, 826, 799, 728, 252, 665, 801, 453, 423, 247, 401, 607, 918, 967, 460, 328, 318, 141, 34, 572, 899, 392, 712, 584, 919, 294, 924, 229, 73, 675, 1, 193, 257, 908, 388, 448, 45, 726, 510, 652, 608, 552, 258, 723, 145, 608, 603, 644, 925, 1, 367, 62, 712, 740, 234, 37, 370, 875, 500, 969, 107, 657, 358, 201, 595, 937, 155, 972, 584, 462, 61, 798, 917, 500, 993, 346, 60, 29, 854, 504, 121, 949, 218, 301, 196, 819, 747, 66, 285, 215, 89, 233, 177, 123, 717, 100, 568, 376, 842, 563, 996, 878, 5, 886, 198, 717, 659, 532, 695, 150, 439, 789, 433, 871, 80, 680, 139, 557, 8, 561, 148, 678, 90, 480, 321, 93, 130, 666, 25, 6102, 428, 945, 947, 682, 128, 499, 172, 423, 511, 72, 370, 548, 599, 66, 879, 678, 559, 784, 4, 22, 745, 660, 812, 599, 218, 683, 638, 411, 227, 405, 387, 323, 568, 785, 637, 626, 211, 193, 142, 517, 525, 812, 159, 725, 214, 165, 505, 173, 489, 249, 789, 394, 944, 934, 451, 697, 660, 100, 259, 486, 626, 872, 183, 102, 24, 152, 27, 63, 676, 928, 17, 699, 859, 227, 500, 988, 106, 723, 284, 792, 685, 829, 847, 912, 547, 306, 195, 584, 256, 413, 40, 656, 903, 53, 182, 751, 403, 225, 715, 218, 195, 726, 79, 222, 497, 519, 769, 64, 651, 413, 570, 682, 232, 144, 619, 688, 51, 739, 694, 402, 719, 393, 639, 661, 926, 462, 654, 274, 163, 165, 107, 631, 589, 758, 944, 647, 402, 201, 826, 193, 907, 966, 961, 155, 829, 645, 865, 543, 68931, 643, 693, 484, 894, 823, 423, 764, 644, 70, 419, 465, 383, 755, 701, 517, 610, 323, 883, 808, 183, 562, 712, 401, 918, 848, 602, 648, 740, 115, 542, 947, 362, 712, 115, 565, 803, 821, 499, 356, 674, 436, 396, 831, 933, 444, 766078, 380, 782, 78, 809, 781, 514, 811, 976, 530, 213, 705, 951, 648, 882, 229, 573, 645, 313, 495, 676, 473, 375, 861, 66, 312, 213, 877, 366, 524, 763, 260, 441, 768, 694, 854, 328, 127, 531, 993, 293, 172, 312, 554, 414, 688, 326, 62, 319, 3, 18, 920, 633, 422, 153, 626, 563, 6, 483, 880, 414, 999, 278, 245, 727, 613, 462, 948, 396, 204, 452, 24, 265, 162, 241, 335, 960, 413, 947, 235, 509, 26, 90, 339, 805, 471, 630, 592, 802, 897, 100, 605, 664, 755, 196, 956, 408, 262, 918, 380, 803, 332, 386, 786, 51, 562, 743, 42, 802, 467, 133, 908, 492, 610, 861, 308, 846, 838, 980, 577, 560, 473489, 734, 827, 166, 738, 998, 329, 364, 783, 557, 686, 81, 41, 933, 652, 378, 648, 268, 294, 378, 331, 257, 822, 807, 460, 153, 207, 785, 868, 704, 295, 296, 841, 104, 391, 382, 452, 322, 430, 235, 239, 2, 297, 282, 825, 386, 236, 918, 323, 920, 51, 993, 330, 829, 28, 560, 683, 784, 916, 113, 634, 143, 864, 758, 598, 77, 965, 511, 767, 121, 202, 908, 887, 436, 483, 992, 82, 431, 775, 352, 551, 616, 738, 195, 821, 859, 17, 931, 616, 509, 557, 978, 261, 663, 783, 188, 567, 872, 983, 434, 924, 957, 474, 327, 642, 422, 416, 71, 651, 807, 982, 679, 433, 57, 408, 233, 423, 969, 963, 595, 484, 999, 787, 656, 609, 173, 568, 432, 874, 314, 624, 691, 991, 385, 397, 730, 127, 809, 152, 291, 93, 753, 620, 341, 503, 349, 265, 698, 600, 832, 577, 320, 830, 778, 900, 692, 525, 517, 230, 790, 958, 293, 534, 923, 147, 57, 529, 81, 471, 837, 934, 957, 34, 189, 117, 592, 400, 907, 482, 76, 810, 804, 411, 255, 132, 974, 833, 334, 484, 393, 101, 657, 744, 829, 345, 844, 313, 640, 725, 944, 111, 526, 737, 777, 574, 276, 765, 954, 210, 630, 678, 95, 54, 510, 329, 849, 532, 910, 404, 516, 825, 591, 204, 578, 384, 395, 966, 923, 618, 674, 308, 896, 920, 853, 492, 268, 934, 847, 615, 787, 193, 800, 67, 127, 180, 582, 403, 934, 762, 591, 699, 657, 772, 823, 127, 81, 666, 117, 328, 460, 902, 549, 489, 704, 774, 704, 185, 111, 517, 640, 872, 643, 868, 896, 483, 735, 561, 619, 174, 408, 645, 962, 863, 304, 68, 995, 336, 856, 210, 439, 373, 935, 340, 861, 755, 182, 543, 743, 342, 364, 975, 964, 82, 81, 880, 865, 381, 488, 653, 522, 539, 542, 160, 562, 933, 759, 96, 43, 989, 337, 627, 409, 594, 446, 187, 158, 956, 658, 628, 390, 308, 472, 178, 640, 283, 226, 364, 187, 16, 516, 590, 434, 260, 541, 733, 621, 294, 69, 664, 609, 565, 842, 348, 368, 961, 532, 544, 957, 974, 158, 455, 90, 328, 759, 735, 949, 881, 290, 523, 4, 804, 103, 668, 26317, 971, 772, 450, 362, 801, 317, 358, 946, 191, 674, 212, 72, 235};
        System.out.println(nums.length);
        long l = System.currentTimeMillis();
        int i = largestPerimeter2(nums);
        System.out.println(System.currentTimeMillis() - l);
        System.out.println(i);
    }

    public int largestPerimeter(int[] nums) {
        Arrays.sort(nums);
        int result = 0;
        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length - 1; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    System.out.println(nums[i] + "," + nums[j] + "," + nums[k]);
                    if (nums[i] + nums[j] > nums[k]) {
                        int i1 = nums[i] + nums[j] + nums[k];
                        if (i1 > result) {
                            result = i1;
                        }
                    }
                }
            }
        }
        return result;
    }


    public int largestPerimeter1(int[] nums) {
        Arrays.sort(nums);
        int result = 0;
        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length - 1; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    System.out.println(nums[i] + "," + nums[j] + "," + nums[k]);
                    if (nums[i] + nums[j] > nums[k]) {
                        int i1 = nums[i] + nums[j] + nums[k];
                        if (i1 > result) {
                            result = i1;
                        }
                    } else {
                        break;
                    }
                }
            }
        }
        return result;
    }

    public int largestPerimeter2(int[] nums) {
        Arrays.sort(nums);
        for (int i = nums.length - 1; i >= 2; i--) {
            if (nums[i - 1] + nums[i - 2] > nums[i]) {
                return nums[i - 1] + nums[i - 2] + nums[i];
            }
        }
        return 0;
    }


    public int maximumWealth(int[][] accounts) {
        int sum = 0;
        for (int i = 0; i < accounts.length; i++) {
            int[] account = accounts[i];
            int temp = 0;
            for (int i1 : account) {
                temp += i1;
            }
            if (temp > sum) {
                sum = temp;
            }
        }
        return sum;
    }

    @org.junit.Test
    public void test49() {
        int[][] mat = {{7, 3, 1, 9}, {3, 4, 6, 9}, {6, 9, 6, 6}, {9, 5, 8, 5}};

//        int[][] mat = {{5}};
        int i = diagonalSum(mat);
        System.out.println(i);
    }

    public int diagonalSum(int[][] mat) {
        int result = 0;
        for (int i = 0; i < mat.length; i++) {
            result += mat[i][i];
            int abs = Math.abs(i - mat.length + 1);
            result += mat[abs][i];
        }
        if (mat.length % 2 != 0) {
            result -= mat[mat.length / 2][mat.length / 2];
        }
        return result;
    }

    public int diagonalSum1(int[][] mat) {
        int result = 0;
        for (int i = 0; i < mat.length; i++) {
            result += mat[i][i];

        }
        for (int i = mat.length - 1; i >= 0; i--) {
            result += mat[i][mat.length - i - 1];
        }
        if (mat.length % 2 != 0) {
            result -= mat[mat.length / 2][mat.length / 2];
        }
        return result;
    }


    @org.junit.Test
    public void test50() {
//        int[][] mat = {{7, 3, 1, 9}, {3, 4, 6, 9}, {6, 9, 6, 6}, {9, 5, 8, 5}};
//        int[][] mat = {{1}, {2}};

//        int[][] mat = {{1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}, {11, 12, 13, 14, 15}, {16, 17, 18, 19, 20}, {21, 22, 23, 24, 25}};


        int[][] mat = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};

//        int[][] mat = {{1, 2, 3}, {4,5, 6}, {7, 8, 9}};

//        int[][] mat = {{1}};
        List<Integer> integers = spiralOrder2(mat);
        System.out.println(integers);
    }

    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        int n = matrix.length;
        int m = matrix[0].length;
        if (n * m == 1) {
            res.add(matrix[0][0]);
            return res;
        }
        int i2 = m * n;
        int i = 0, j = 0, d = 0;
        int i1 = i, j1 = j;
        int num = m * n - (m - 2) * (n - 2);
        while (d < i2) {
            for (int k = 0; k < num && d < i2; k++) {
                res.add(matrix[i][j]);
                if (j < m - 1 && i == i1) {
                    j++;
                } else if (j == m - 1 && i < n - 1) {
                    i++;
                } else if (i == n - 1 && j > j1) {
                    j--;
                } else if (j == j1 && i > i1) {
                    i--;
                }
                d++;
            }
            i = ++i1;
            j = ++j1;
            m--;
            n--;
            num = (m - 1) * (n - 1) - (m - 3) * (n - 3);
        }
        return res;
    }

    public List<Integer> spiralOrder1(int[][] matrix) {
        List<Integer> order = new ArrayList<Integer>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return order;
        }
        int rows = matrix.length, columns = matrix[0].length;
        boolean[][] visited = new boolean[rows][columns];
        int total = rows * columns;
        int row = 0, column = 0;
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int directionIndex = 0;
        for (int i = 0; i < total; i++) {
            order.add(matrix[row][column]);
            visited[row][column] = true;
            int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];
            if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn]) {
                directionIndex = (directionIndex + 1) % 4;
            }
            row += directions[directionIndex][0];
            column += directions[directionIndex][1];
        }
        return order;
    }

    public List<Integer> spiralOrder2(int[][] matrix) {
        List<Integer> res = new ArrayList<>();

        int top = 0;
        int bottom = matrix.length - 1;
        int left = 0;
        int right = matrix[0].length - 1;

        while (top <= bottom && left <= right) {
            for (int i = left; i <= right; i++) {
                res.add(matrix[top][i]);
            }
            top++;
            for (int i = top; i <= bottom; i++) {
                res.add(matrix[i][right]);
            }
            right--;
            for (int i = right; i >= left && top <= bottom; i--) {
                res.add(matrix[bottom][i]);
            }
            bottom--;
            for (int i = bottom; i >= top && left <= right; i--) {
                res.add(matrix[i][left]);
            }
            left++;
        }
        return res;
    }

    @org.junit.Test
    public void test51() {
        int[][] ints = generateMatrix(3);
        Arrays.stream(ints).forEach(i -> System.out.println(Arrays.toString(i)));
    }

    public int[][] generateMatrix(int n) {
        int[][] result = new int[n][n];
        int top = 0;
        int bottom = n - 1;
        int left = 0;
        int right = n - 1;
        int k = 1;
        while (top <= bottom && left <= right) {
            for (int i = left; i <= right; i++) {
                result[top][i] = k++;
            }
            top++;
            for (int i = top; i <= bottom; i++) {
                result[i][right] = k++;
            }
            right--;
            for (int i = right; i >= left && top <= bottom; i--) {
                result[bottom][i] = k++;
            }
            bottom--;
            for (int i = bottom; i >= top && left <= right; i--) {
                result[i][left] = k++;
            }
            left++;
        }
        return result;
    }

    public void setZeroes(int[][] matrix) {
        boolean[] x = new boolean[matrix.length];
        boolean[] y = new boolean[matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == 0) {
                    x[i] = true;
                    y[j] = true;
                }
            }
        }
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (x[i] || y[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }

    public void setZeroes1(int[][] matrix) {
        int[][] temp = new int[matrix.length][matrix[0].length];

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] != 0) {
                    temp[i][j] = matrix[i][j];
                }
            }
        }
        matrix = temp;
    }


    @org.junit.Test
    public void test52() {
        int[][] board = {{0, 1, 0}, {0, 0, 1}, {1, 1, 1}, {0, 0, 0}};
        gameOfLife(board);

        System.out.println();


    }


    public void gameOfLife(int[][] board) {
        int n = board.length;
        int m = board[0].length;

        int[][] temp = new int[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int oneNum = 0;
                //当前位置
                int value = board[i][j];
                //上
                if (i - 1 >= 0) {
                    if (board[i - 1][j] == 1) {
                        oneNum++;
                    }
                }
                //下
                if (i + 1 < n) {
                    if (board[i + 1][j] == 1) {
                        oneNum++;
                    }
                }

                if (j - 1 >= 0) {
                    //左
                    if (board[i][j - 1] == 1) {
                        oneNum++;
                    }
                    //左上
                    if (i - 1 >= 0) {
                        if (board[i - 1][j - 1] == 1) {
                            oneNum++;
                        }
                    }
                    //左下
                    if (i + 1 < n) {
                        if (board[i + 1][j - 1] == 1) {
                            oneNum++;
                        }
                    }
                }

                if (j + 1 < m) {
                    //右
                    if (board[i][j + 1] == 1) {
                        oneNum++;
                    }
                    //右下
                    if (i + 1 < n) {
                        if (board[i + 1][j + 1] == 1) {
                            oneNum++;
                        }
                    }
                    //右上
                    if (i - 1 >= 0) {
                        if (board[i - 1][j + 1] == 1) {
                            oneNum++;
                        }
                    }
                }

                if (oneNum < 2) {
                    temp[i][j] = 0;
                }
                if (oneNum == 2) {
                    temp[i][j] = value;
                }
                if (oneNum == 3) {
                    temp[i][j] = 1;
                }
                if (oneNum > 3) {
                    temp[i][j] = 0;
                }
            }
        }


        System.arraycopy(temp, 0, board, 0, temp.length);
    }

    /**
     * 时间复杂度为O(n*n)
     * 空间复杂度为O(n)
     */
    public void rotate(int[] nums, int k) {
        int[] temp = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            temp[i] = nums[i];
        }
        for (int i = 0; i < temp.length; i++) {
            nums[(i + k) % temp.length] = temp[i];
        }
    }

    @org.junit.Test
    public void test53() {
//        int[] nums = {1, 2, 3, 4, 5, 6, 7};
        int[] nums = {-1, -100, 3, 99};
        rotate1(nums, 2);
        System.out.println();
    }


    public void rotate1(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }

    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int num = nums[start];
            nums[start] = nums[end];
            nums[end] = num;
            start++;
            end--;
        }
    }

    @org.junit.Test
    public void test54() {
        long l = System.currentTimeMillis();
        int i = countOdds(0, 1000000000);
        System.out.println(System.currentTimeMillis() - l);
        System.out.println(i);
    }

    public int countOdds(int low, int high) {
        int count = 0;
        for (int i = low; i <= high; i++) {
            if ((i & 1) != 0) {
                count++;
            }
        }
        return count;
    }

    public int countOdds1(int low, int high) {
        if ((high - low + 1) % 2 == 0) {
            return (high - low) / 2;
        } else {
            int i = (high - low) / 2;
            if (high % 2 == 0) {
                return i;
            } else {
                return i + 1;
            }
        }
    }

    @org.junit.Test
    public void test55() {
        long l = System.currentTimeMillis();
        int[] bills = {5, 5, 5, 10, 20};
        boolean b = lemonadeChange(bills);
        System.out.println(System.currentTimeMillis() - l);
        System.out.println(b);
    }

    public boolean lemonadeChange(int[] bills) {
        int fiveNum = 0;
        int tenNum = 0;
        int twentyNUm = 0;

        for (int i = 0; i < bills.length; i++) {
            int change = bills[i] - 5;
            if (change != 0) {
                boolean flag = false;
                mark:
                for (int j = 0; j <= fiveNum; j++) {
                    for (int k = 0; k <= tenNum; k++) {
                        if (change == j * 5 + k * 10) {
                            flag = true;
                            fiveNum -= j;
                            tenNum -= k;
                            break mark;
                        }
                    }
                }
                if (!flag) {
                    return false;
                }
            }
            if (bills[i] == 5) {
                fiveNum++;
            } else if (bills[i] == 10) {
                tenNum++;
            } else {
                twentyNUm++;
            }
        }
        return true;
    }

    @org.junit.Test
    public void test56() {
        long l = System.currentTimeMillis();
        int[] bills = {1000, 2000, 3000};
        double average = average(bills);
        System.out.println(System.currentTimeMillis() - l);
        System.out.println(average);
    }

    public double average(int[] salary) {
        Arrays.sort(salary);
        int num = 0;
        for (int i = 1; i < salary.length - 1; i++) {
            num += salary[i];
        }
        return num / salary.length;
    }


    @org.junit.Test
    public void test57() {
        long l = System.currentTimeMillis();
        String multiply = multiply("123456789", "987654321");
        System.out.println(System.currentTimeMillis() - l);
        System.out.println(multiply);
    }

    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        char[] chars1 = num1.toCharArray();
        char[] chars2 = num2.toCharArray();
        return multiply(chars1, chars2);
    }

    private String multiply(char[] chars1, char[] chars2) {
        if (chars1.length < chars2.length) {
            return multiply(chars2, chars1);
        }

        //相乘
        List<StringBuilder> temp = new ArrayList<>();
        int carry = 0;
        for (int j = chars2.length - 1; j >= 0; j--) {
            StringBuilder sb = new StringBuilder();
            for (int k = 0; k < Math.abs(j - chars2.length + 1); k++) {
                sb.append("0");
            }
            for (int i = chars1.length - 1; i >= 0; i--) {
                int i1 = (chars1[i] - '0') * (chars2[j] - '0') + carry;
                sb.append(i1 % 10);
                carry = i1 / 10;
            }
            if (carry != 0) {
                sb.append(carry);
                carry = 0;
            }
            temp.add(sb.reverse());
        }

        //相加
        carry = 0;
        StringBuilder start = temp.get(0).reverse();
        for (int i = 1; i < temp.size(); i++) {
            StringBuilder s = temp.get(i).reverse();
            char[] chars = s.toString().toCharArray();
            char[] chars3 = start.toString().toCharArray();
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < chars.length || j < chars3.length; j++) {
                int result = 0;
                if (j < chars.length) {
                    result += chars[j] - '0';
                }
                if (j < chars3.length) {
                    result += chars3[j] - '0';
                }
                result += carry;
                sb.append(result % 10);
                carry = result / 10;
            }
            if (carry != 0) {
                sb.append(carry);
                carry = 0;
            }
            start = sb;
        }
        return start.reverse().toString();
    }


    @org.junit.Test
    public void test58() {
        long l = System.currentTimeMillis();
        String multiply = multiply1("1234", "567");
        System.out.println(System.currentTimeMillis() - l);
        System.out.println(multiply);
    }

    public String multiply1(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        int m = num1.length(), n = num2.length();
        int[] ansArr = new int[m + n];
        for (int i = m - 1; i >= 0; i--) {
            int x = num1.charAt(i) - '0';
            for (int j = n - 1; j >= 0; j--) {
                int y = num2.charAt(j) - '0';
                ansArr[i + j + 1] += x * y;
            }
        }
        for (int i = m + n - 1; i > 0; i--) {
            ansArr[i - 1] += ansArr[i] / 10;
            ansArr[i] %= 10;
        }
        int index = ansArr[0] == 0 ? 1 : 0;
        StringBuffer ans = new StringBuffer();
        while (index < m + n) {
            ans.append(ansArr[index]);
            index++;
        }
        return ans.toString();
    }


    public String addStrings(String num1, String num2) {
        int m = num1.length();
        int n = num2.length();
        StringBuilder sb = new StringBuilder();
        int carry = 0;
        while (m - 1 >= 0 || n - 1 >= 0) {
            int i1 = m - 1 >= 0 ? num1.charAt(m - 1) - '0' : 0;
            int i2 = n - 1 >= 0 ? num2.charAt(n - 1) - '0' : 0;
            int i = i1 + i2 + carry;
            sb.append(i % 10);
            carry = i / 10;
            n--;
            m--;
        }
        if (carry != 0) {
            sb.append(carry);
        }
        return sb.reverse().toString();
    }

    @org.junit.Test
    public void test59() {
        long l = System.currentTimeMillis();
        String multiply = addStrings1("1", "9");
        System.out.println(System.currentTimeMillis() - l);
        System.out.println(multiply);
    }

    public String addStrings1(String num1, String num2) {
        int max = Math.max(num1.length(), num2.length());
        int[] ints = new int[max + 1];

        char[] arr1 = num1.toCharArray();
        char[] arr2 = num2.toCharArray();

        int m = arr1.length;
        int n = arr2.length;

        int carry = 0;
        while (m - 1 >= 0 || n - 1 >= 0) {
            int i1 = m - 1 >= 0 ? arr1[m - 1] - '0' : 0;
            int i2 = n - 1 >= 0 ? arr2[n - 1] - '0' : 0;
            int i = i1 + i2 + carry;
            ints[max] = i % 10;
            carry = i / 10;
            n--;
            m--;
            max--;
        }
        if (carry != 0) {
            ints[0] = carry;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = carry != 0 ? 0 : 1; i < ints.length; i++) {
            sb.append(ints[i]);
        }
        return sb.toString();
    }


    @org.junit.Test
    public void test60() {
        ListNode result = new ListNode(2);
        ListNode result1 = new ListNode(4);
        ListNode result2 = new ListNode(3);
        result.next = result1;
        result1.next = result2;

        ListNode node = new ListNode(5);
        ListNode node1 = new ListNode(6);
        ListNode node2 = new ListNode(4);
        node.next = node1;
        node1.next = node2;

        ListNode listNode = addTwoNumbers(result, node);
        System.out.println();
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode result = new ListNode();
        ListNode pre = result;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int val1 = l1 == null ? 0 : l1.val;
            int val2 = l2 == null ? 0 : l2.val;
            int i = val1 + val2 + carry;
            int i1 = i % 10;
            carry = i / 10;
            result.next = new ListNode(i1);
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
            result = result.next;
        }

        if (carry != 0) {
            result.next = new ListNode(carry);
        }
        return pre.next;
    }

    public ListNode addTwoNumbers1(ListNode l1, ListNode l2) {
        //定义一个新的节点，把该节点当做返回链表的头部。
        ListNode pre = new ListNode(0);
        //定义一个新的节点，指向链表的头部。
        ListNode cur = pre;
        //进位
        int carry = 0;
        while (l1 != null || l2 != null) {
            //因为不知道那个数据为null，所以需要做非null判断。
            int x = l1 == null ? 0 : l1.val;
            int y = l2 == null ? 0 : l2.val;
            int sum = x + y + carry;

            carry = sum / 10;
            sum = sum % 10;

            //这一步需要注意
            //把当前计算的值，放到了cur的next中。
            cur.next = new ListNode(sum);
            //把cur的next赋值给了cur。也就是说cur变量指向了next对象。
            cur = cur.next;

            //因为不知道那个数据为null，所以需要做非null判断。
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        //进位不为空，加到链表的尾部。
        if (carry == 1) {
            cur.next = new ListNode(carry);
        }
        return pre.next;
    }


    @org.junit.Test
    public void test61() {
        String str = "abcabcabcabc";
        repeatedSubstringPattern(str);
    }

    public boolean repeatedSubstringPattern(String s) {
        int n = s.length();
        for (int i = 1; i * 2 <= n; ++i) {
            if (n % i == 0) {
                boolean match = true;
                for (int j = i; j < n; ++j) {
                    char c = s.charAt(j);
                    char c1 = s.charAt(j - i);
                    if (c != c1) {
                        match = false;
                        break;
                    }
                }
                if (match) {
                    return true;
                }
            }
        }
        return false;
    }

    @org.junit.Test
    public void test62() {
        double v = myPow1(2.0, -2147483648);
        System.out.println(v);
    }

    public double myPow(double x, int n) {
        if (x == 0.0f) {
            return 0.0d;
        }

        long b = n;
        double res = 1.0;
        if (b < 0) {
            x = 1 / x;
            b = -b;
        }
        while (b > 0) {
            if ((b & 1) == 1) {
                res *= x;
            }
            x *= x;
            b >>= 1;
        }
        return res;
    }

    public double myPow1(double x, int n) {
        long m = n;
        m = m < 0 ? -m : m;
        double res = 1.0;
        int i = 0;
        while (m > 0) {
            if (m % 2 == 1) {
                res = res * x;
            }
            x *= x;
            m = m / 2;
            i++;
        }

        if (n < 0) {
            res = 1 / res;
        }
        System.out.println("i=" + i);
        return res;
    }

    public double myPow2(double x, int n) {
        long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }

    public double quickMul(double x, long N) {
        if (N == 0) {
            return 1.0;
        }
        double y = quickMul(x, N / 2);
        return N % 2 == 0 ? y * y : y * y * x;
    }

    @org.junit.Test
    public void test63() {
        String[] arr = new String[]{"5", "2", "C", "D", "+"};
        Integer v = calPoints1(arr);
        System.out.println(v);
    }

    public int calPoints(String[] operations) {
        List<Integer> list = new ArrayList<>();
        int j = 0;
        for (int i = 0; i < operations.length; i++) {
            String str = operations[i];
            switch (str) {
                case "+":
                    list.add(list.get(j - 1) + list.get(j - 2));
                    j++;
                    break;
                case "D":
                    list.add(list.get(j - 1) * 2);
                    j++;
                    break;
                case "C":
                    list.remove(j - 1);
                    j--;
                    break;
                default:
                    list.add(Integer.parseInt(str));
                    j++;
                    break;
            }
        }
        return list.stream().reduce((x, y) -> x += y).get();
    }

    public int calPoints1(String[] operations) {
        int[] arr = new int[operations.length];
        int j = 0;
        for (int i = 0; i < operations.length; i++) {
            String str = operations[i];
            switch (str) {
                case "+":
                    arr[j] = arr[j - 1] + arr[j - 2];
                    j++;
                    break;
                case "D":
                    arr[j] = arr[j - 1] * 2;
                    j++;
                    break;
                case "C":
                    j--;
                    break;
                default:
                    arr[j] = Integer.parseInt(str);
                    j++;
                    break;
            }
        }
        int result = 0;
        for (int i = j - 1; i >= 0; i--) {
            result += arr[i];
        }
        return result;
    }

    public boolean judgeCircle(String moves) {
        int x = 0;
        int y = 0;
        for (int i = 0; i < moves.length(); i++) {
            switch (moves.charAt(i)) {
                case 'U':
                    y++;
                    break;
                case 'D':
                    y--;
                    break;
                case 'R':
                    x--;
                    break;
                case 'L':
                    x++;
                    break;
                default:
                    break;
            }
        }
        return x == 0 && y == 0;
    }

    @org.junit.Test
    public void test64() {
//        int[][] moves =   {{0,0},{2,0},{1,1},{2,1},{2,2}};
//        int[][] moves = {{0, 0}, {1, 1}, {0, 1}, {0, 2}, {1, 0}, {2, 0}};
//        int[][] moves = {{0, 0}, {1, 1}, {2, 0}, {1, 0}, {1, 2}, {2, 1}, {0, 1}, {0, 2}, {2, 2}};
//        int[][] moves = {{1, 0}, {2, 2}, {2, 0}, {0, 1}, {1, 1}};
        int[][] moves = {{2, 2}, {0, 2}, {1, 0}, {0, 1}, {2, 0}, {0, 0}};
        String tictactoe = tictactoe(moves);
        System.out.println(tictactoe);
    }

    public String tictactoe(int[][] moves) {
        if (moves.length < 5) {
            return "Pending";
        }
        int length = moves.length;
        //A的棋子
        int a = 0;
        int[][] A = new int[length / 2 + length % 2][2];
        //B的棋子
        int b = 0;
        int[][] B = new int[length / 2][2];
        for (int i = 0; i < length; i++) {
            int[] move = moves[i];
            if (i % 2 == 0) {
                A[a] = move;
                a++;
            } else {
                B[b] = move;
                b++;
            }
        }
        if (A.length >= 3) {
            for (int i = 0; i < A.length - 2; i++) {
                for (int j = i + 1; j < A.length; j++) {
                    for (int k = j + 1; k < A.length; k++) {
                        if (A[i][0] == A[j][0] && A[i][0] == A[k][0]) {
                            return "A";
                        }
                        if (A[i][1] == A[j][1] && A[i][1] == A[k][1]) {
                            return "A";
                        }
                        if (A[i][0] == A[i][1] && A[j][0] == A[j][1] && A[k][0] == A[k][1]) {
                            return "A";
                        }
                        if (A[i][0] + A[i][1] == 2 && A[j][0] + A[j][1] == 2 && A[k][0] + A[k][1] == 2) {
                            return "A";
                        }
                    }
                }
            }
        }
        if (B.length >= 3) {
            for (int i = 0; i < B.length - 2; i++) {
                for (int j = i + 1; j < B.length; j++) {
                    for (int k = j + 1; k < B.length; k++) {
                        if (B[i][0] == B[j][0] && B[i][0] == B[k][0]) {
                            return "B";
                        }
                        if (B[i][1] == B[j][1] && B[i][1] == B[k][1]) {
                            return "B";
                        }
                        if (B[i][0] == B[i][1] && B[j][0] == B[j][1] && B[k][0] == B[k][1]) {
                            return "B";
                        }
                        if (B[i][0] + B[i][1] == 2 && B[j][0] + B[j][1] == 2 && B[k][0] + B[k][1] == 2) {
                            return "B";
                        }
                    }
                }
            }
        }
        if (moves.length == 9) {
            return "Draw";
        } else {
            return "Pending";
        }

    }

    @org.junit.Test
    public void test65() {
//                int[][] moves =   {{0,0},{2,0},{1,1},{2,1},{2,2}};
//        int[][] moves = {{0, 0}, {1, 1}, {0, 1}, {0, 2}, {1, 0}, {2, 0}};
//        int[][] moves = {{0, 0}, {1, 1}, {2, 0}, {1, 0}, {1, 2}, {2, 1}, {0, 1}, {0, 2}, {2, 2}};
//        int[][] moves = {{1, 0}, {2, 2}, {2, 0}, {0, 1}, {1, 1}};
//        int[][] moves = {{2, 2}, {0, 2}, {1, 0}, {0, 1}, {2, 0}, {0, 0}};
        int[][] moves = {{1, 2}, {2, 1}, {1, 0}, {0, 0}, {0, 1}, {2, 0}, {1, 1}};
        String tictactoe = tictactoe1(moves);
        System.out.println(tictactoe);
    }


    String[] victory = new String[]{
            "111000000",
            "000111000",
            "000000111",
            "100100100",
            "010010010",
            "001001001",
            "100010001",
            "001010100"
    };

    int[] victory1 = new int[]{448, 56, 7, 292, 146, 73, 273, 84};

    public String tictactoe1(int[][] moves) {

        int length = moves.length;
        if (length < 5) {
            return "Pending";
        }
        StringBuilder aStr = new StringBuilder("000000000");
        StringBuilder bStr = new StringBuilder("000000000");
        for (int i = 0; i < length; i++) {
            int[] move = moves[i];
            if (move[0] == 0 && move[1] == 0) {
                if (i % 2 == 0) {
                    aStr.replace(0, 1, "1");
                } else {
                    bStr.replace(0, 1, "1");
                }
            }
            if (move[0] == 0 && move[1] == 1) {
                if (i % 2 == 0) {
                    aStr.replace(1, 2, "1");
                } else {
                    bStr.replace(1, 2, "1");
                }
            }
            if (move[0] == 0 && move[1] == 2) {
                if (i % 2 == 0) {
                    aStr.replace(2, 3, "1");
                } else {
                    bStr.replace(2, 3, "1");
                }
            }
            if (move[0] == 1 && move[1] == 0) {
                if (i % 2 == 0) {
                    aStr.replace(3, 4, "1");
                } else {
                    bStr.replace(3, 4, "1");
                }
            }
            if (move[0] == 1 && move[1] == 1) {
                if (i % 2 == 0) {
                    aStr.replace(4, 5, "1");
                } else {
                    bStr.replace(4, 5, "1");
                }
            }
            if (move[0] == 1 && move[1] == 2) {
                if (i % 2 == 0) {
                    aStr.replace(5, 6, "1");
                } else {
                    bStr.replace(5, 6, "1");
                }
            }
            if (move[0] == 2 && move[1] == 0) {
                if (i % 2 == 0) {
                    aStr.replace(6, 7, "1");
                } else {
                    bStr.replace(6, 7, "1");
                }
            }
            if (move[0] == 2 && move[1] == 1) {
                if (i % 2 == 0) {
                    aStr.replace(7, 8, "1");
                } else {
                    bStr.replace(7, 8, "1");
                }
            }
            if (move[0] == 2 && move[1] == 2) {
                if (i % 2 == 0) {
                    aStr.replace(8, 9, "1");
                } else {
                    bStr.replace(8, 9, "1");
                }
            }
        }

        int a = Integer.parseInt(aStr.toString(), 2);
        int b = Integer.parseInt(bStr.toString(), 2);

        if (length > 4) {
            for (int num : victory1) {
                if ((a & num) == num) {
                    return "A";
                }
                if ((b & num) == num) {
                    return "B";
                }
            }
        }
        if (moves.length == 9) {
            return "Draw";
        } else {
            return "Pending";
        }
    }


    @org.junit.Test
    public void test66() {
        int[] arr = new int[]{1, 3, 2};
        int i = removeDuplicates(arr);
        System.out.println(i);
    }

    public int removeDuplicates(int[] nums) {
        int i = 0, j = 0;
        for (; i < nums.length; i++) {
            if (nums[i] != nums[j]) {
                j++;
                nums[j] = nums[i];
            }
        }
        return ++j;
    }

    @org.junit.Test
    public void test67() {
        int[] arr = new int[]{3, 2, 3};
        int i = majorityElement(arr);
        System.out.println(i);
    }

    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        int temp = nums[0];
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == temp) {
                count++;
            } else if (nums[i] != temp) {
                count = 1;
                temp = nums[i];
            }
            if (count > nums.length / 2) {
                return temp;
            }
        }
        return -1;
    }


    @org.junit.Test
    public void test68() {
        int[] arr = new int[]{7, 1, 5, 3, 6, 4};
        int i = maxProfit1(arr);
        System.out.println(i);
    }

    public int maxProfit(int[] prices) {
        return split1(prices, 0, prices.length - 1);
    }

    private int split(int[] prices, int start, int end) {
        if (start == end) {
            return 0;
        }
        int max = prices[start];
        int index = start;
        for (int i = start; i < prices.length; i++) {
            if (prices[i] > max) {
                index = i;
                max = prices[i];
            }
        }
        if (index > start && index < end) {
            int split = split(prices, start, index);
            int split1 = split(prices, index + 1, end);
            return split > split1 ? split : split1;
        } else if (index == start) {
            return split(prices, index + 1, end);
        } else if (index == end) {
            int res = 0;
            for (int i = 0; i < end - start; start++) {
                if (prices[end] - prices[start] > res) {
                    res = prices[end] - prices[start];
                }
            }
            return res;
        }
        return 0;
    }


    public int maxProfit1(int[] prices) {
        int min = prices[0];
        int result = 0;
        int max = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] < prices[i - 1]) {
                min = prices[i];
                result += max;
                max = 0;
            } else if (prices[i] - min > max) {
                max = prices[i] - min;
            }
        }

        return result + max;
    }


    private int split1(int[] prices, int start, int end) {
        if (start == end) {
            return 0;
        }
        int max = prices[start];
        int index = start;
        for (int i = start; i < prices.length; i++) {
            if (prices[i] > max) {
                index = i;
                max = prices[i];
            }
        }
        if (index > start && index < end) {
            int split = split1(prices, start, index);
            int split1 = split1(prices, index + 1, end);
            return split + split1;
        } else if (index == start) {
            return split1(prices, index + 1, end);
        } else if (index == end) {
            int res = 0;
            for (int i = 0; i < end - start; start++) {
                if (prices[end] - prices[start] > res) {
                    res = prices[end] - prices[start];
                }
            }
            return res;
        }
        return 0;
    }


    @org.junit.Test
    public void test69() {
        int[] arr = new int[]{0};
        boolean b = canJump1(arr);
        System.out.println(b);
    }

    public boolean canJump(int[] nums) {
        int length = nums.length;
        int index = nums.length;
        for (int i = length - 1; i >= 0; i--) {
            if (nums[i] >= index - i) {
                index = i;
            } else {
                continue;
            }
        }
        return index == 0;
    }

    public boolean canJump1(int[] nums) {
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i <= index) {
                if (nums[i] + i >= index) {
                    index = nums[i] + i;
                    if (index >= nums.length - 1) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    public boolean canJump2(int[] nums) {
        int n = nums.length;
        int rightmost = 0;
        for (int i = 0; i < n; ++i) {
            if (i <= rightmost) {
                rightmost = Math.max(rightmost, i + nums[i]);
                if (rightmost >= n - 1) {
                    return true;
                }
            }
        }
        return false;
    }

    @org.junit.Test
    public void test70() {
        int[] citations = new int[]{100};
        int i = hIndex(citations);
        System.out.println(i);
    }

    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int hindex = 0;
        for (int i = 0; i < citations.length; i++) {

            if (citations.length - i + 1 > citations[i]) {
                hindex = i;
            }

        }
        return hindex;
    }

    @org.junit.Test
    public void test71() {
        String str = "0P";
        boolean palindrome = isPalindrome1(str);
        System.out.println(palindrome);
    }

    public boolean isPalindrome(String s) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if ((c >= '0' && c <= '9') || (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z')) {
                sb.append(c);
            }
        }
        String s1 = sb.toString().toLowerCase();
        if (s1.equals("")) {
            return true;
        }
        StringBuilder s2 = new StringBuilder(s1).reverse();
        return s2.toString().equals(s1);
    }

    public boolean isPalindrome1(String s) {
        if (s.equals("")) {
            return true;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if ((c >= '0' && c <= '9') || (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z')) {
                sb.append(c);
            }
        }
        if (sb.length() == 0 || sb.length() == 1) {
            return true;
        }
        String s1 = sb.toString().toLowerCase();
        for (int i = 0; i < s1.length() / 2; i++) {
            char c = s1.charAt(i);
            if (s1.charAt(i) != s1.charAt(s1.length() - 1 - i)) {
                return false;
            }
        }
        return true;
    }

    public boolean isPalindrome2(String s) {
        StringBuffer sgood = new StringBuffer();
        int length = s.length();
        for (int i = 0; i < length; i++) {
            char ch = s.charAt(i);
            if (Character.isLetterOrDigit(ch)) {
                sgood.append(Character.toLowerCase(ch));
            }
        }
        StringBuffer sgood_rev = new StringBuffer(sgood).reverse();
        return sgood.toString().equals(sgood_rev.toString());
    }

    public int maximumNumberOfStringPairs(String[] words) {
        HashSet<Integer> indexSet = new HashSet<>();
        int count = 0;
        for (int i = 0; i < words.length; i++) {
            if (indexSet.contains(i)) {
                continue;
            }
            StringBuilder sb = new StringBuilder(words[i]).reverse();
            String tempStr = sb.toString();
            for (int j = i + 1; j < words.length; j++) {
                if (indexSet.contains(j)) {
                    continue;
                }
                if (tempStr.equals(words[j])) {
                    indexSet.add(i);
                    indexSet.add(j);
                    count++;
                }
            }
        }
        return count;
    }

    @org.junit.Test
    public void test72() {
        String[] strings = {"cd", "ac", "dc", "ca", "zz"};
        int i = maximumNumberOfStringPairs1(strings);
        System.out.println(i);
    }

    public int maximumNumberOfStringPairs1(String[] words) {
        int count = 0;
        Map<String, Integer> map = new HashMap<>();

        for (int i = 0; i < words.length; i++) {
            map.put(words[i], i);
        }
        for (int i = 0; i < words.length; i++) {
            String s = new StringBuilder(words[i]).reverse().toString();
            if (map.get(s) != null && map.get(s) > i) {
                count++;
            }
        }
        return count;
    }

    @org.junit.Test
    public void test73() {
        isSubsequence("b", "abc");
    }

    public boolean isSubsequence(String s, String t) {
        int j = 0;
        for (int i = 0; i < t.length() && j < s.length(); i++) {
            if (t.charAt(i) == s.charAt(j)) {
                j++;
            }
        }
        return j == s.length();
    }

    public int[] twoSum(int[] numbers, int target) {
        for (int i = 1; i <= numbers.length; i++) {
            int num = target - numbers[i - 1];
            for (int j = i + 1; j <= numbers.length; j++) {
                if (numbers[j - 1] == num) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{-1, -1};
    }


    @org.junit.Test
    public void test74() {
        int[] ints = {2, 7, 11, 15};
        int target = 9;
        long l = System.currentTimeMillis();
        int[] ints1 = twoSum1(ints, 9);
        System.out.println(System.currentTimeMillis() - l);
        System.out.println(Arrays.toString(ints1));
    }

    public int[] twoSum1(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; i++) {
            int low = i + 1;
            int high = numbers.length - 1;
            while (low <= high) {
                int mid = (high - low) / 2 + low;
                if (numbers[mid] == target - numbers[i]) {
                    return new int[]{i + 1, mid + 1};
                } else if (numbers[mid] > target - numbers[i]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
        }
        return new int[]{-1, -1};
    }

    public int maxArea(int[] height) {
        int max = 0;
        for (int i = 0; i < height.length; i++) {
            for (int j = i + 1; j < height.length; j++) {
                int high = height[i] < height[j] ? height[i] : height[j];
                int width = j - i;
                max = high * width > max ? high * width : max;
            }
        }
        return max;
    }


    public int maxArea1(int[] height) {
        int max = 0;

        for (int i = 0; i < height.length; i++) {

        }
        return max;
    }

    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            int low = 0;
            int high = nums.length - 1;
            while (low < i && i < high) {
                if (nums[low] + nums[high] == -num) {
                    List<Integer> item = new ArrayList<>();
                    item.add(nums[i]);
                    item.add(nums[low]);
                    item.add(nums[high]);
                    result.add(item);
                    high--;
                } else if (nums[low] + nums[high] > -num) {
                    high--;
                } else {
                    low++;
                }
            }
        }

        result = result.stream().distinct().collect(Collectors.toList());
        return result;
    }


    @org.junit.Test
    public void test75() {
        canConstruct("aa", "ab");
    }

    public boolean canConstruct(String ransomNote, String magazine) {
        int[] arr = new int[26];
        for (int i = 0; i < magazine.length(); i++) {
            arr[magazine.charAt(i) - 'a']++;
        }
        for (int i = 0; i < ransomNote.length(); i++) {
            arr[ransomNote.charAt(i) - 'a']--;
            if (arr[ransomNote.charAt(i) - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }


    public boolean isIsomorphic(String s, String t) {
        //判断数组长度是否相等
        if (s.length() != t.length()) {
            return false;
        }

        //存储映射关系
        int[] arr = new int[128];
        //存储字符是否已经被映射过
        int[] arr1 = new int[128];

        for (int i = 0; i < s.length(); i++) {
            //字符对应位置为0，表明该字符还未设置映射关系
            if (arr[s.charAt(i)] == 0) {
                //判断需要映射的字符，是否已经被映射过，如果被映射过返回false，没有则设置映射关系。
                if (arr1[t.charAt(i)] == 0) {
                    arr[s.charAt(i)] = t.charAt(i);
                    arr1[t.charAt(i)]++;
                } else {
                    return false;
                }
            } else if (arr[s.charAt(i)] != t.charAt(i)) {
                //不相等，表明映射关系不对
                return false;
            }
        }
        return true;
    }


    public boolean wordPattern(String pattern, String s) {
        String[] sArr = s.split(" ");
        if (pattern.length() != sArr.length) {
            return false;
        }
        HashMap<Character, String> patternMap = new HashMap<>(26);
        HashMap<String, Character> sPatternMap = new HashMap<>(sArr.length);

        for (int i = 0; i < pattern.length(); i++) {
            if (patternMap.get(pattern.charAt(i)) == null) {
                if (sPatternMap.get(sArr[i]) == null) {
                    patternMap.put(pattern.charAt(i), sArr[i]);
                    sPatternMap.put(sArr[i], pattern.charAt(i));
                } else {
                    return false;
                }
            } else {
                if (!patternMap.get(pattern.charAt(i)).equals(sArr[i])) {
                    return false;
                }
            }
        }
        return true;
    }

    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res = new ArrayList<>();
        HashMap<String, List<String>> map = new HashMap<>();
        for (int i = 0; i < strs.length; i++) {
            String str = strs[i];
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            List<String> list = map.get(Arrays.toString(chars));
            if (list != null && list.size() > 0) {
                list.add(str);
            } else {
                list = new ArrayList<>();
                list.add(str);
                map.put(Arrays.toString(chars), list);
            }
        }
        res.addAll(map.values());
        return res;
    }

    public List<List<String>> groupAnagrams1(String[] strs) {
        List<List<String>> res = new ArrayList<>();
        Map<String, Integer> map = new HashMap<>();
        map.put("a", 2);
        map.put("b", 3);
        map.put("c", 4);
        map.put("d", 7);
        map.put("e", 11);
        map.put("f", 13);
        map.put("g", 17);
        map.put("h", 19);
        map.put("i", 23);
        map.put("j", 29);
        map.put("k", 31);
        map.put("l", 37);
        map.put("m", 41);
        map.put("n", 43);
        map.put("o", 47);
        map.put("p", 53);
        map.put("q", 59);
        map.put("r", 61);
        map.put("s", 67);
        map.put("t", 71);
        map.put("u", 73);
        map.put("v", 79);
        map.put("w", 83);
        map.put("x", 89);
        map.put("y", 97);
        map.put("z", 101);

        HashMap<Integer, List<String>> temp = new HashMap<>();
        for (String str : strs) {

        }

        return res;
    }


    public boolean isAnagram1(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        int a = 0;
        for (int i = 0; i < s.length(); i++) {
            char c1 = s.charAt(i);
            char c = t.charAt(i);
            a = a ^ c ^ c1;
        }
        return a == 0;
    }

    public boolean containsNearbyDuplicate(int[] nums, int k) {
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < nums.length; i++) {
            if (list.contains(nums[i])) {
                return true;
            }
            list.add(nums[i]);
            if (list.size() - k > 0) {
                list.remove(0);
            }
        }
        return false;
    }

    public boolean isValid(String s) {
        List<Character> res = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{') {
                res.add(c);
            } else {
                if (res.size() == 0) {
                    return false;
                }
                Character character = res.get(res.size() - 1);
                if (character == '(' && c != ')') {
                    return false;
                }
                if (character == '{' && c != '}') {
                    return false;
                }
                if (character == '[' && c != ']') {
                    return false;
                }
                res.remove(res.size() - 1);
            }
        }
        return res.size() == 0;
    }

    public boolean isValid1(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(')');
            } else if (c == '{') {
                stack.push('}');
            } else if (c == '[') {
                stack.push(']');
            } else if (stack.empty() || c != stack.pop()) {
                return false;
            }
        }
        return stack.empty();
    }

    @org.junit.Test
    public void test76() {
        simplifyPath("/../");
    }

    public String simplifyPath(String path) {
        Stack<String> stack = new Stack<>();
        String[] split = path.split("/");
        for (int i = 0; i < split.length; i++) {
            switch (split[i]) {
                case ".":
                case "":
                    break;
                case "..":
                    if (!stack.isEmpty()) {
                        stack.pop();
                    }
                    break;
                default:
                    stack.push(split[i]);
                    break;
            }
        }
        if (stack.size() > 0) {
            Iterator<String> iterator = stack.iterator();
            StringBuilder sb = new StringBuilder();
            while (iterator.hasNext()) {
                sb.append("/").append(iterator.next());
            }
            return sb.toString();
        }
        return "/";
    }

    @org.junit.Test
    public void test77() {
        int i = maximumSwap(98368);
        System.out.println(i);
    }

    public int maximumSwap(int num) {
        char[] swap = swap(String.valueOf(num).toCharArray(), 0);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < swap.length; i++) {
            sb.append(swap[i]);
        }
        return Integer.parseInt(sb.toString());
    }

    public char[] swap(char[] chars, int start) {
        if (start >= chars.length) {
            return chars;
        }
        int index = 0;
        char max = 0;
        for (int i = start; i < chars.length; i++) {
            if (chars[i] >= max) {
                max = chars[i];
                index = i;
            }
        }

        for (int i = start; i < index; i++) {
            if (chars[i] < chars[index]) {
                char temp = chars[i];
                chars[i] = max;
                chars[index] = temp;
                return chars;
            }
        }
        return swap(chars, index + 1);
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

@Data
class WeLeadsCenterGtasksSaveAndSendParam {

    /**
     * 线索Id
     */
    private Long leadsId;

    /**
     * 用户Id
     */
    private Long userId;

    /**
     * 企微用户Id
     */
    private String weUserId;

    /**
     * 待办任务通知类型
     * 0：线索长时间未完成首次跟进
     * 1: 线索长时间未完成后续跟进
     * 2：线索长时间未到店
     * 3：长时间未添加线索好友
     */
    private Integer type;

    /**
     * 线索所属公海Id
     */
    private Long seaId;

    /**
     * 公海规则版本号
     */
    private Integer version;

    /**
     * 是否保护期 true是，false否
     */
    private Boolean isProtect;

    /**
     * 计算结束时间
     */
    private Date endTime;

}






